package com.lsa.cormen.ch24.samples;

import java.io.IOException;
import java.util.LinkedList;
import java.util.List;

import com.lsa.helpers.IConverter;
import com.lsa.helpers.graph.IGraph;
import com.lsa.helpers.graph.TgfGraphFactory;

public class DagShortestPath {
    private static int time = 0; 
    public static void main(String[] args) throws IOException {
        final IGraph<VData, EData> g = TgfGraphFactory.readGraphFromFile("data/samples/cormen/ch24/shortest/bellman_ford/input.tgf", new IConverter<String, VData>() {
            @Override
            public VData convert(String data) {
                final VData vData = new VData();
                vData.v = Integer.valueOf(data);
                return vData;
            }
        }, new IConverter<String, EData>() {
            @Override
            public EData convert(String data) {
                return new EData(Integer.valueOf(data));
            }
            }, 
            true
        );
        
        LinkedList<Integer> topSorted = new LinkedList<Integer>();
        dfs(g, 0, topSorted);
        
        for (int i = 1; i <= topSorted.size(); i++) {
            System.out.print(String.format("%2s ", i) );
        }
        
        System.out.println();
        
        int ord = 0;
        for (Integer u : topSorted) {
            g.nodeAttr(u).ord = ord++;
            System.out.print(String.format("%2s ", u) );
        }
        
        g.nodeAttr(0).dist = 0;
        for (Integer u : topSorted) {
            List<Integer> adj = g.adjacencyList(u);
            for (Integer v : adj) {
                if (g.nodeAttr(v).dist > g.nodeAttr(u).d + g.edgeAttr(u, v).w) {
                    g.nodeAttr(v).pred = u;
                    g.nodeAttr(v).dist = g.nodeAttr(u).d + g.edgeAttr(u, v).w;
                }
            }
        }
        
        VData vdata;
        int u = 15;
        while(true) {
            vdata = g.nodeAttr(u);
            if (vdata.pred != -1) {
                EData edata = g.edgeAttr(vdata.pred, u);
                edata.label = edata.label + " ***";
            }
            else{
                break;
            }
            u = vdata.pred;
        }
        
        TgfGraphFactory.saveGraphAsTgf(g, new IConverter<VData, String>() {
            @Override
            public String convert(VData data) {
                return ""+data.v + " "+data.f + String.format("(%s)", data.ord);
            }
        }, new IConverter<EData, String>() {

            @Override
            public String convert(EData data) {
                return ""+data.label;
            }
        }, "data/samples/small_tmp_topsort.tgf");
        
    }
    
    public static void dfs(IGraph<VData, EData> g, int u, LinkedList<Integer> topSorted) {
        List<Integer> adj = g.adjacencyList(u);
        
        g.nodeAttr(u).c = Color.GRAY; 
        g.nodeAttr(u).d = ++time;
        
        for (Integer v : adj) {
            if (Color.WHITE == g.nodeAttr(v).c) {
                dfs(g, v, topSorted);
            }
        }
        
        g.nodeAttr(u).c = Color.BLACK;
        g.nodeAttr(u).f = ++time;
        
        topSorted.addFirst(u);
    }
    
    public static enum Color{
        WHITE,
        GRAY,
        BLACK
    }
    
    private static class VData {
        int pred = -1;
        int v;
        int ord;
        
        Color c = Color.WHITE;
        
        int dist = Integer.MAX_VALUE / 2 - 1; // distance
        
        int d; // discovery time
        int f; // finish time
        
        private VData() {
        }
    }
    
    private static class EData {
        int w;
        String label ="";
        
        public EData(int w) {
            this.w = w;
            label = label + w;
        }
    }
}
